Problems tagged with "best and worst case"

What is the best case time complexity of the following function in terms of \(n\)?

def foo(arr):
    """`arr` is a list containing n numbers."""
    previous = None
    n = len(arr)
    for x in arr:
        if x == previous:
            for i in range(n**2):
                print('Equal!')
            return
        previous = x

What is the worst case time complexity of the function in the previous problem?

True or False: the best case time complexity of mergesort is \(\Theta(n)\).

The below code takes in an array of numbers and returns the index of the first maximum. What is this code's best case time complexity?

def index_of_maximum(arr):
    """`arr` is an array with n elements."""
    for i, x in enumerate(arr):
        if x == max(arr):
            return i

The below code takes in an array of numbers and returns the index of the first maximum.

def foo(arr):
    """`arr` is an array with n elements."""
    for i, x in enumerate(arr):
        if x == max(arr):
            return i

What is the worst case time complexity of the function?

The code below takes in an array of \(n\) numbers and checks whether there is a pair of numbers in the array which, when added together, equal the maximum element of the array.

What is the best case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.

def exists_pair_summing_to_max(arr):
    n = len(arr)
    maximum = max(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == maximum:
                return True
    return False

What is the worst case time complexity of the function in the last problem? State your answer using asymptotic notation.

What is the best case time complexity of the following function in terms of \(n\)?

def foo(arr):
    """`arr` is a list containing n numbers."""
    previous = None
    n = len(arr)
    for x in arr:
        if x == previous:
            for i in range(n**2):
                print('Equal!')
            return
        previous = x

True or False: the best case time complexity of mergesort is \(\Theta(n)\).